package lc_1054_距离相等的条形码;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class Solution {

	public int[] rearrangeBarcodes(int[] barcodes) {
		Map<Integer, Integer> counter = new HashMap<>();
		for (int num : barcodes) {
			counter.merge(num, 1, Integer::sum);
		}
		int len = barcodes.length;
		int[] ans = new int[len];
		PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> b[1] - a[1]);
		for (Map.Entry<Integer, Integer> entry : counter.entrySet()) {
			Integer key = entry.getKey();
			Integer val = entry.getValue();
			queue.add(new int[] { key, val });
		}
		for (int i = 0; i < len; i++) {
			int[] f = queue.poll();
			if (i == 0 || ans[i - 1] != f[0]) {
				ans[i] = f[0];
				if (--f[1] > 0) {
					queue.add(f);
				}
			} else {
				int[] s = queue.poll();
				ans[i] = s[0];
				if (--s[1] > 0) {
					queue.add(s);
				}
				queue.add(f);
			}
		}
		return ans;
	}

	public static void main(String[] args) {

//		String str = "[1,1,1,2,2,2]";
//		Solution so = new Solution();
//		String print = Arrays.toString(so.rearrangeBarcodes(ids));
//		System.out.println(print);
	}

}